﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace PrimaryAlgorithm.LevelOrder
{
    class MainProject
    {
        static void Main(string[] args)
        {
            TreeNode treeNode = new TreeNode(1, new TreeNode(2, new TreeNode(3), new TreeNode(5)), new TreeNode(2, new TreeNode(4), new TreeNode(3)));
            Console.WriteLine(LevelOrder(treeNode));
            Console.ReadKey();
        }
        /// <summary>
        /// BFS
        /// </summary>
        /// <param name="root"></param>
        /// <returns></returns>
        public static IList<IList<int>> LevelOrder(TreeNode root)
        {
          
            Queue<TreeNode> treeNodes = new Queue<TreeNode>();

            treeNodes.Enqueue(root);
            IList<IList<int>> rootList = new List<IList<int>>();
            if (root == null)
            {
                return rootList;
            }
            while (treeNodes.Count>0)
            {
                List<int> list = new List<int>();
                int size = treeNodes.Count;
                for (int i = 0; i < size; i++)
                {
                    TreeNode treeNode = treeNodes.Dequeue();
                    list.Add(treeNode.val);
                    if (treeNode.left!=null)
                    {
                        treeNodes.Enqueue(treeNode.left);
                    }
                    if (treeNode.right != null)
                    {
                        treeNodes.Enqueue(treeNode.right);
                    }
                }
                rootList.Add(list);
            }
            return rootList;
        }
    }
}
